#ifndef BITMAP_H
#define BITMAP_H

#include <algorithm>
#include <string>
#include <string.h>

template<size_t Bits_>
class my_bitset_t
{
    public:
        enum {
            Bits = Bits_,
            Uint32s = Bits_ / 32 + 1
        };

        my_bitset_t()
            :_uint32_num(0), _1num(0)
        {
            clear();
        }

        bool any()
        {
            return _1num > 0;
        }

        void clear()
        {
            _1num = 0;
            memset(_uints, 0, Uint32s * 4);
        }

        void set()
        {
            _1num = Uint32s * 4 * 32;
            memset(_uints, -1, Uint32s * 4);
        }

        my_bitset_t &set(size_t pos_, bool val_ = true)
        {
            size_t uint32_idx = pos_/32;
            size_t uint32_offset = pos_%32;

            bool old_val = ((_uints[uint32_idx] & (1 << uint32_offset)) != 0);
            if (old_val == val_)
                return *this;

            if(val_)
            {
                ++_1num;

                _uints[uint32_idx] |= 1 << uint32_offset;

                _uint32_num = std::max(size_t(_uint32_num), uint32_idx+1);
            }
            else
            {
                --_1num;
                _uints[uint32_idx] &= ~(1 << uint32_offset);

                if(uint32_idx+1 < _uint32_num)
                {
                }
                else
                {
                    for(size_t i=size_t(_uint32_num)-1; i != -1; --i)
                    {
                        if(_uints[i] != 0)
                        {
                            _uint32_num = i+1;
                            break;
                        }
                    }
                }
            }

            return *this;
        }

        bool test(size_t pos_)
        {
            size_t uint32_idx = pos_/32;
            size_t uint32_offset = pos_%32;

            return (_uints[uint32_idx] & (1 << uint32_offset)) != 0;
        }
    
        size_t get_1num() {
            return _1num;
        }

        size_t uint32_num()
        {
            return _uint32_num;
        }

        uint32_t get_uint32(size_t index_)
        {
            return _uints[index_];
        }

        void set_uint32(size_t index_, uint32_t uint32_)
        {
            _uints[index_] = uint32_;
            if(uint32_) {
                _uint32_num = std::max(size_t(_uint32_num), index_+1);
                _1num += _calc_1_num(uint32_);
            }
        }

        void export_array(uint32_t* array_)
        {
            for(size_t i=0; i<_uint32_num; ++i)
            {
                array_[i] = _uints[i];
            }
        }

        void import_array(uint32_t* array_, size_t num_)
        {
            _1num = 0;
            _uint32_num = num_;
            for(size_t i=0; i<num_; ++i)
            {
                _uints[i] = array_[i];
                _1num += _calc_1_num(_uints[i]);
            }
        }

        const std::string &to_string()
        {
            _string = "";
            for(size_t i=0; i<Uint32s; ++i)
            {
                uint32_t bit = 1;
                for(size_t j=0; j<32; ++j)
                {
                    if(bit<<j & _uints[i])
                        _string.append("1");
                    else
                        _string.append("0");
                }
            }

            return _string;
        }

        void import_string(const std::string &string_)
        {
            _1num = 0;
            size_t len = string_.length();
            const char* str = string_.c_str();
            for(size_t i=0; i<len; ++i)
            {
                if(str[i] != '0')
                {
                    set(i, true);
                    ++_1num;
                }
            }
        }


    private:
        uint32_t _calc_1_num(uint32_t mask) {
            uint32_t total = 0;
            if (mask == (uint32_t) -1)
                total += 32;
            else {
                for (int j=0; j<32; ++j) {
                    if (mask & (1<<j))
                        ++total;
                }
            }
            return total;
        }

        uint32_t _1num;
        uint32_t _uints[Uint32s];
        uint32_t _uint32_num;
        std::string _string;
};

#endif
